package cn.lishiyuan.algorithm.sort;

import java.util.List;

/**
 * 冒泡排序
 * <br>
 * 冒泡排序的思路是，比较相邻两个元素，如果满足交换条件则交换。
 * <br>
 * 每次遍历，会将最大或者最小的元素移动到最后。
 */
public class BubbleSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {

        // 第一轮就将元素放到了最后，所以最后一个元素不要遍历，如果只有一个元素那更不需要遍历了

        for (int i = 0; i < data.size() - 1 ; i++) {

            boolean flag = true;

            for (int j = 0 ; j < (data.size()  - i - 1) ; j++) {
                T left = data.get(j);
                T right = data.get( j + 1 );
                // 也就是右边比左边大，那么要交换位置
                if(right.compareTo(left) < 0){
                    data.set(j, right);
                    data.set(j+1, left);
                    flag = false;
                }
            }
            // 某轮没有没有交换则提前返回
            if(flag){
                return data;
            }
        }

        return data;
    }

    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {
        // 第一轮就将元素放到了最后，所以最后一个元素不要遍历，如果只有一个元素那更不需要遍历了
        for (int i = 0; i < data.length - 1 ; i++) {
            boolean flag = true;
            for (int j = 0; j < (data.length - i - 1) ; j++) {
                T left = data[j];
                T right = data[ j + 1 ];
                // 也就是右边比左边大，那么要交换位置
                if(right.compareTo(left) < 0){
                    data[j] = right;
                    data[j+1] = left;
                    flag = false;
                }
            }
            // 某轮没有没有交换则提前返回
            if(flag){
                return data;
            }
        }

        return data;
    }
}
